[统计学习]第五章决策树

决策树是一种解决分类和回归问题的方法，它是基于特征对实例进行划分以生成树结构。决策树的模型实现需要从特征选择、树生成以及剪枝等三个部分，特征选择依赖于不同的算法作出选择。在应用上决策树可以生成基于特征的规则，这种条件规则可以被应用于生产场景。

1. ID3 算法

ID3 算法（Quinlan 1986）是一个自顶向下构造决策树来进行学习，构造过程需要解决的问题是“哪个特征作为树节点”。特征选择的方法是通过计算信息增益的方法进行，决策树构建是一个递归的过程。

1.1 信息增益

在理解信息增益之前需要弄清楚熵（Entropy）的含义。熵在信息论和概率统计中衡量随机变量的不确定性，其意义上是对随机变量的纯度体现。

对一个离散随机变量 $X$，对每一个类别可以得到的概率为 $P(X=x_i)=p_i, i=1,2,\cdots,n$，对于该变量的熵的计算：

$H(p)=-\displaystyle{\sum_{i=1}^n(p_i \log p_i)}$

熵越大，那么说明随机变量的纯度越低，它的不确定性越大。而信息增益（Information Gain）是表示的是已知随机变量的信息下，使得目标的不确定性减少的程度。信息增益的数学表达式为 $G(Y, X)=H(Y)-H(Y|X)$，即在条件熵的降低了原有的熵大小:

$$
\begin{align}
G(Y,X)=&H(Y) - H(Y|X) \
H(Y|X)=&\sum_{i=1}^n(p_i H(Y|X=x_i)) \
H(Y)=&-\sum_{i=1}^n(p_i \log p_i)
\end{align}
$$

1.2 信息增益筛选特征

下图是以是否打网球及其他特征统计信息，以此信息作为计算示例：

1. 是否打网球的类别比为 $9:5$，那么在根结点上得到的熵值为 $H(\text{PlayTennis})=-(\frac{5}{14}\log\frac{5}{14} + \frac{9}{14}\log\frac{9}{14})$
2. 计算选择不同特征的信息增益
   *